\bigskip
\bigskip
{\magonebf 5.9 Sets of nodes and edges (node\_set, edge\_set)}


An instance $S$ of the data type $node\_set$ ($edge\_set$) is a subset of 
the nodes (edges) of a graph $G$. $S$ is said to be valid for the nodes 
(edges) of $G$.


\bigskip
{\bf 1. Creation of a node or edge set}

$node\_set$ $S(G)$;\nl
$edge\_set$ $S(G)$;

creates an instance $S$ of type $node\_set$  ($edge\_set$) valid for all nodes
(edges) currently contained in graph $G$ and initializes it to the empty set. 


\bigskip
\def\var{$S$}
{\bf 2. Operations on a node/edge set S}
\medskip
\+\op void insert {x}                 
                                {adds node (edge) $x$ to $S$}
\smallskip
\+\op void del {x}                    
                                {removes node (edge) $x$ from $S$}
\smallskip
\+\op bool member {x}                 
                                {returns true if $x$ in $S$, false otherwise}
\smallskip
\+\op node/edge choose {}                 
                                {return a node (edge) of $S$}
\smallskip
\+\op int  size  {}                  
                                {returns the size of $S$}
\smallskip
\+\op bool  empty {}                  
                                {returns true iff $S$ is the empty set}
\smallskip
\+\op void clear {}                   
                                {makes $S$ the empty set}

\bigskip
{\bf 3. Implementation}

A node (edge) set $S$ for a graph $G$ is implemented by a combination of a 
list  $L$ of nodes (edges) and a node (edge) array of list\_items 
associating with each node (edge) its position in $L$. All operations 
take constant time, except of clear which takes time $O(|S|)$. The space 
requirement is $O(n)$, where $n$ is the number of nodes (edges) of $G$.


\vfill\eject


